#include <iostream>
#include <vector>
#include <queue>

/**
 * @details 找出一个数组中的第K大的数
 */

int topK1(std::vector<int> &nums, int k)
{
    // 建立K个数的小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
    for (auto &x : nums)
    {
        pq.push(x);
        if (pq.size() > k)
        {
            pq.pop();
        }
    }

    return pq.top();
}

int topK2(std::vector<int> &nums, int k)
{
    // 建立nums.size()个数的大堆,pop() k次
    std::priority_queue<int> pq(nums.begin(), nums.end());
    for (int i = 0; i < k; i++)
    {
        pq.pop();
    }
    return pq.top();
}

int main()
{
    std::vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int ans1 = topK1(nums, 2);
    int ans2 = topK1(nums, 3);
    std::cout << "数组中第2大的数字为: " << ans1 << std::endl;
    std::cout << "数组中第3大的数字为: " << ans2 << std::endl;
    return 0;
}
